class Solution:
    def maxNumber(self, nums1: list[int], nums2: list[int], k: int) -> list[int]:
        m,n=len(nums1),len(nums2)
        # 找到数组中长度为k且字典序最大的集合
        def findKth(k,nums):
            nn=len(nums)
            stack=[]
            for i,num in enumerate(nums):
                # 必须保证栈中元素和剩下元素总长度之和不小于k
                while stack and stack[-1]<num and len(stack)-1+nn-i>=k:
                    stack.pop()
                stack.append(num)
            return stack[:k]
        
        # 根据字典序合并两个数组
        def merge(a,b):
            m_,n_=len(a),len(b)
            res=[]
            i,j=0,0
            # 比较字典序
            while i<m_ and j<n_:
                if a[i:]>b[j:]:
                    res.append(a[i])
                    i+=1
                else:
                    res.append(b[j])
                    j+=1
            if i<m_:
                res.extend(a[i:])
            if j<n_:
                res.extend(b[j:])
            return res
        
        # 遍历两个数组
        ans=[]
        for i in range(m+1):
            if 0<=k-i<=n:        
                ans=max(ans,merge(findKth(i,nums1),findKth(k-i,nums2)))
        return ans
